﻿#include <iostream>
#include <vector>

using namespace std;

static vector<int> getAllNumbersFromText(const char* text)
{
	int index = 0;
	char strNum[100] = { 0 };
	int numIndex = 0;
	auto strSize = strlen(text);
	vector<int> numbers;
	int num = 0;
	while (index < strSize)
	{
		if (text[index] == ' ')
		{
			sscanf_s(strNum, "%d", &num);
			numbers.push_back(num);
			memset(strNum, 0, 100);
			numIndex = 0;
			num = 0;
			++index;
			continue;
		}

		strNum[numIndex++] = text[index++];
	}

	sscanf_s(strNum, "%d", &num);
	numbers.push_back(num);
	return numbers;
}

static vector<int> numbersNotAppeared(int* numbers, size_t numCount)
{
	vector<int> notAppeared;
	int index = 0;
	int tmpNum1 = 0;
	int index1 = 0;
	int index2 = 0;
	int tmpNum2 = 0;
	while (index < numCount)
	{
		if (numbers[index] == index + 1)
		{
			++index;
			continue;
		}

		index1 = numbers[index] - 1;
		tmpNum1 = numbers[index];
		while (numbers[index1] != index1 + 1)
		{
			index2 = numbers[index1] - 1;
			tmpNum2 = numbers[index1];
			numbers[index1] = tmpNum1;
			index1 = index2;
			tmpNum1 = tmpNum2;
		}

		++index;
	}

	for (int i = 0; i < numCount; i++)
	{
		if (numbers[i] != i + 1)
		{
			notAppeared.push_back(i + 1);
		}
	}

	return notAppeared;
}

/**
 * 给定一个整数数组A，长度是n，有1<=A[i]<=n, 且对于[1,n]的整数，其中部分整数会重复出现而部分不会出现。
 * 实现算法找到[1,n]中所有未出现在A中的整数。
 * 提示: 尝试实现O(n)的时间复杂度和O(1)的空间复杂度(返回值不计入空间复杂度)。
 *
 * 输入描述:
 * 一行数字，全部为整数，空格分隔
 * A0 A1 A2 A3 ...
 * 输出描述:
 * 一行数字，全部为整数，空格分隔
 * R0 R1 R2 R3 ...
 *
 * 示例:
 * 输入
 * 1 3 4 3
 * 输出
 * 2
 *
 * 思路:
 * 从索引0到n-1遍历，在i位置，看当前这个数字是否是i+1, 如果是，则继续处理A[i+1];
 * 如果不是，跳至A[A[i]-1]处,
 * 设tmp = A[A[i]-1], 如果tmp == A[i] 则继续处理A[i+1];
 * 如果不相等，则将A[i]赋值给A[A[i]-1], 再跳到A[tmp-1]的地方，如此反复操作...
 * 跳到了k位置，如果k位置的数字是预期的k+1, 则继续处理A[i+1]
 */
int main_FindNumberNotAppeared()
{
	char input[1000] = "1 1 1 1 1";
	auto numbers = getAllNumbersFromText(input);
	auto notAppeared = numbersNotAppeared((int*)(&numbers[0]), numbers.size());
	for (auto it = notAppeared.begin(); it != notAppeared.end(); it++)
	{
		printf("%d ", *it);
	}

	return 0;
}